Iterative Reweighted Minimization Methods for $l_p$ Regularized Unconstrained Nonlinear Programming

摘要

In this paper we study general $l_p$ regularized unconstrained minimizationproblems. In particular, we derive lower bounds for nonzero entries of first-and second-order stationary points, and hence also of local minimizers of the$l_p$ minimization problems. We extend some existing iterative reweighted $l_1$(IRL1) and $l_2$ (IRL2) minimization methods to solve these problems andproposed new variants for them in which each subproblem has a closed formsolution. Also, we provide a unified convergence analysis for these methods. Inaddition, we propose a novel Lipschitz continuous $\epsilon$-approximation to$\|x\|^p_p$. Using this result, we develop new IRL1 methods for the $l_p$minimization problems and showed that any accumulation point of the sequencegenerated by these methods is a first-order stationary point, provided that theapproximation parameter $\epsilon$ is below a computable threshold value. Thisis a remarkable result since all existing iterative reweighted minimizationmethods require that $\epsilon$ be dynamically updated and approach zero. Ourcomputational results demonstrate that the new IRL1 method is generally morestable than the existing IRL1 methods [21,18] in terms of objective functionvalue and CPU time.